// 又是一道好久之前的题
#include <bits/stdc++.h>
using namespace std;

// 求最小值，转换为求最长路
// 求解差分约束问题都要将条件转化为x>=y+k（求最小值、最长路）或x<=y+l（求最大值、最短路）（k为常数，这样才能确定边的长度）
// 差分约束问题中，如果出现环（最长路正环，最短路负环）则无解
using ll = long long;
const int R = 1e5 + 10;
struct Ch
{
	int x, a, b;
} a[R];
struct Edge
{
	int to, len;
};
vector<Edge> v[R], son[R];
int cnt[R], dfn[R], low[R], tme, belong[R], sta[R], top, scc, rd[R];
ll dis[R];
void tarjan(int x)
{
	dfn[x] = low[x] = ++tme;
	sta[++top] = x;
	for (Edge to : v[x])
	{
		if (!dfn[to.to])
		{
			tarjan(to.to);
			low[x] = min(low[x], low[to.to]);
		}
		else if (!belong[to.to])
		{
			low[x] = min(low[x], dfn[to.to]);
		}
	}
	if (dfn[x] == low[x])
	{
		++scc;
		while (sta[top] != x)
		{
			belong[sta[top]] = scc;
			++cnt[scc]; // 统计当前分量中点的个数，到时候这个分量里的小朋友分的糖果数一样
			--top;
		}
		belong[x] = scc;
		++cnt[scc];
		--top;
	}
}
void topo()
{
	queue<int> q;
	for (int i = 1; i <= scc; ++i)
	{
		if (!rd[i])
		{
			q.push(i);
		}
	}
	int x;
	while (!q.empty())
	{
		x = q.front();
		q.pop();
		for (Edge to : son[x])
		{
			dis[to.to] = max(dis[x] + to.len, dis[to.to]); // 这里求的是最长路，所以是max
			if (!(--rd[to.to]))
			{
				q.push(to.to);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, k, x, y, i;
	char op;
	cin >> n >> k;
	for (i = 1; i <= k; ++i)
	{
		cin >> op >> x >> y;
		if (op == '1') // x==y -> x>=y+0 && y>=x+0
		{
			v[x].push_back({y, 0});
			v[y].push_back({x, 0});
		}
		else if (op == '2') // x<y -> x<=y-1 -> y>=x+1
		{
			v[x].push_back({y, 1});
			if (x == y)
			{
				cout << "-1";
				return 0;
			}
		}
		else if (op == '3') // x>=y -> x>=y+0
		{
			v[y].push_back({x, 0});
		}
		else if (op == '4') // x>y -> x>=y+1
		{
			v[y].push_back({x, 1});
			if (x == y)
			{
				cout << "-1";
				return 0;
			}
		}
		else // x<=y -> y>=x+0
		{
			v[x].push_back({y, 0});
		}
	}
	// 建立超级原点0，使得每一条边都能走到，且到每一个点的长度为1（因为每个小朋友至少有1个糖果）
	for (i = 1; i <= n; ++i)
	{
		v[0].push_back({i, 1}); // dis[i]>=dis[0]+1
	}
	tarjan(0);
	for (i = 0; i <= n; ++i)
	{
		for (Edge to : v[i])
		{
			if (belong[i] == belong[to.to] && to.len) // 在一个环里，还要有人比另一个人多，无法满足
			{
				cout << "-1";
				return 0;
			}
			if (belong[i] != belong[to.to])
			{
				son[belong[i]].push_back({belong[to.to], to.len});
				++rd[belong[to.to]];
			}
		}
	}
	topo();
	ll ans = 0;
	for (i = 1; i <= scc; ++i)
	{
		ans += dis[i] * cnt[i];
	}
	cout << ans << flush;
	return 0;
}
